#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
    int maxProfit(vector<int>& prices, int fee) 
    {
        int n = prices.size();
        vector<int> f(n), g(n);
        f[0] = -prices[0];
        for(int i = 1; i < n; ++i)
        {
            f[i] = max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = max(g[i - 1], f[i - 1] - fee + prices[i]);
        }
        return g[n - 1];
    }
};

// 877. 石子游戏
class Solution 
{
public:
    bool stoneGame(vector<int>& piles) 
    {
        int n = piles.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for(int i = 0; i < n; ++i) dp[i][i] = piles[i];

        for(int i = n - 1; i >= 0; --i)
        {
            for(int j = i + 1; j < n; ++j)
            {
                dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] >= 0;
    }
};

// 931. 下降路径最小和
class Solution 
{
public:
    int minFallingPathSum(vector<vector<int>>& matrix) 
    {
        int n = matrix.size(), memo[n][n];
        memset(memo, 0x3f, sizeof memo);
        function<int(int, int)> dfs = [&](int r, int c){
            if(c < 0 || c >= n) return INT_MAX;
            if(r == 0) return matrix[0][c];
            int& ret = memo[r][c];
            if(ret != 0x3f3f3f3f) return ret;
            return ret = min(min(dfs(r - 1, c - 1), dfs(r - 1, c)), dfs(r - 1, c + 1)) + matrix[r][c];
        };

        int ans = INT_MAX;
        for(int c = 0; c < n; ++c) ans = min(ans, dfs(n - 1, c));
        return ans;
    }
};